/*
 * quickSort.hpp
 *
 *  Created on: Sep 12, 2011
 *      Author: dgdiniz
 */

#ifndef QUICKSORT_HPP_
#define QUICKSORT_HPP_

#include "utility/utility.hpp"

namespace playlib
{

template<typename T>
void quickSort(T list[], const unsigned length)
{
	if (length <=1) return;

	unsigned low = 1;
	unsigned high = length-1;
	unsigned pivot = 0;

	while (low <= high)
	{
		if (list[low] < list[pivot]) low++;
		else if (list[high] > list[pivot]) high--;
		else swap(list[low], list[high]);
	}
	swap(list[high], list[pivot]);

	if (high > 1) quickSort(list, high);
	if (length-high-1 > 1) quickSort(list+high+1, length-high-1);
}

template<typename T>
void quickSortDec(T list[], const unsigned length)
{
	if (length <=1) return;

	unsigned low = 1;
	unsigned high = length-1;
	unsigned pivot = 0;

	while (low <= high)
	{
		if (list[low] > list[pivot]) low++;
		else if (list[high] < list[pivot]) high--;
		else swap(list[low], list[high]);
	}
	swap(list[high], list[pivot]);

	if (high > 1) quickSortDec(list, high);
	if (length-high-1 > 1) quickSortDec(list+high+1, length-high-1);
}

}


#endif /* QUICKSORT_HPP_ */
